package interview.lingxing;

/**
 * 使用快排进行排序
 */
public class Test3 {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 1, 4, 5, 3};
        // 原地排序 在原数组空间内进行排序
        quickSort(nums);
        for (int num : nums) {
            System.out.print(num + ",");
        }
    }

    /**
     * 快排对外暴露函数
     *
     * @param nums 排序数组
     */
    public static void quickSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        helper(nums, 0, nums.length - 1);
    }

    /**
     * 快排递归函数
     *
     * @param nums
     * @param start
     * @param end
     */
    private static void helper(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0) {
            return;
        }
        if (start >= end) {
            return;
        }
        int p = partition(nums, start, end);
        helper(nums, start, p - 1);
        helper(nums, p + 1, end);
    }

    /**
     * 获取分区点
     *
     * @param nums
     * @param start 排序起始位置
     * @param end   排序结束位置
     * @return
     */
    private static int partition(int[] nums, int start, int end) {
        int p = end;

        int i = start, j = start;

        for (; i < end; i++) {
            if (nums[i] <= nums[p]) {
                swapArray(nums, i, j);
                j++;
            }
        }

        swapArray(nums, j, p);
        return j;
    }

    /**
     * 交换数组中的两个元素位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private static void swapArray(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
